package com.leetcode.partition8;

import java.util.*;

/**
 * @author `RKC`
 * @date 2021/7/28 11:05
 */
public class LC720词典中最长的单词 {

    public static void main(String[] args) {
        String[] arr = {"a", "banana", "app", "appl", "ap", "apply", "apple"};
        System.out.println(longestWord(arr));
    }

    public static String longestWord(String[] words) {
        if (words.length == 0) return "";
        return trie(words);
    }

    private static String trie(final String[] words) {
        String answer = "";
        TrieNode root = new TrieNode(' '), cur = root;
        for (String s : words) {
            char[] word = s.toCharArray();
            //构建字典树
            for (int j = 0; j < word.length; j++) {
                if (cur.trieNodeMap.containsKey(word[j])) {
                    if (j == word.length - 1) cur.trieNodeMap.get(word[j]).end = true;
                    cur = cur.trieNodeMap.get(word[j]);
                    continue;
                }
                TrieNode trieNode = new TrieNode(word[j]);
                if (j == word.length - 1) trieNode.end = true;
                cur.trieNodeMap.put(word[j], trieNode);
                cur = cur.trieNodeMap.get(word[j]);
            }
            cur = root;
        }
        //字典树的查找
        boolean end;
        for (String word : words) {
            cur = root;             //当前指针重新指向根结点
            if (word.length() > answer.length() || (word.length() == answer.length() && compare(word, answer) < 0)) {
                end = true;
                for (char ch : word.toCharArray()) {
                    cur = cur.trieNodeMap.get(ch);
                    if (!cur.end) {
                        end = false;
                        break;
                    }
                }
                if (end) answer = word;
            }
        }
        return answer;
    }

//    private static String trie(String[] words) {
//        TireNode root = new TireNode();
//        TireNode current;
//        //字典树构建完毕，进行查找
//        String result = "";
//        boolean isWord;
//        for (String word : words) {
//            current = root;
//            if (word.length() > result.length() || (word.length() == result.length() && compare(word, result) < 0)) {
//                isWord = true;
//                //在字典树中查找当前word的每个字符
//                for (char c : word.toCharArray()) {
//                    current = current.tireNodes.get(c);
//                    if (!current.end) {
//                        //从root到current的字符组成的单词没有在字典中
//                        isWord = false;
//                        break;
//                    }
//                }
//                if (isWord) result = word;
//            }
//        }
//        return result;
//    }

    private static class TrieNode {
        Map<Character, TrieNode> trieNodeMap = new HashMap<>();
        boolean end;
        char data;

        public TrieNode(char data) {
            this.data = data;
        }
    }

    private static String violence(String[] words) {
        //将单词添加到HashSet，便于后续查找
        Set<String> set = new HashSet<String>();
        set.addAll(Arrays.asList(words));
        String result = "";
        boolean isWord;
        for (String word : words) {
            //当前遍历的单词长度比result大，或者相等时，当前单词小于result，就检测是否符合题意
            if (word.length() > result.length() || (word.length() == result.length() && compare(word, result) < 0)) {
                isWord = true;
                //对当前word的各个子串进行查找，是否在HashSet中存在
                for (int i = 1; i < word.length(); i++) {
                    if (!set.contains(word.substring(0, i))) {
                        //当前子串不存在，直接跳出循环
                        isWord = false;
                        break;
                    }
                }
                //当前word的子串也满足要求，对result重新赋值
                if (isWord) result = word;
            }
        }
        return result;
    }

    public static int compare(String str1, String str2) {
        char[] arr1 = str1.toCharArray();
        char[] arr2 = str2.toCharArray();
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return arr1[i] - arr2[i];
            }
        }
        return 0;
    }
}
